package collection;

import java.util.HashMap;
import java.util.Map;

/**
 * 哈希双向链表
 *
 * @author jiangwz
 * @create 2021/2/26.
 */
public class MyLRUCacheDemo {

    class Node<K, V> {
        private int key;
        private int val;
        private Node<K, V> prev;
        private Node<K, V> next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }

        @Override
        public String toString() {
            return key + "=" + val;
        }
    }

    class DoubleLinkList<K, V> {
        private Node<K, V> head;
        private Node<K, V> tail;

        public DoubleLinkList() {
        }

        //把某个节点加到头
        public void addHead(Node<K, V> node) {
            if (head == null && tail == null) {
                head = tail = node;
            } else {
                Node<K, V> pred = head;
                head = node;
                node.next = pred;
                pred.prev = node;
            }
        }



        // 移除某个节点
        public void remove(Node<K, V> node){
            Node<K, V> prev = node.prev;
            Node<K, V> next = node.next;
            if (node == head) {
                head = next;
            }
            if (node == tail) {
                tail = prev;
            }
            if (prev != null){
                prev.next = next;
            }
            if (next != null) {
                next.prev = prev;
            }

            /**
             * prev=右
             * next=左
             */

            node.next = null;
            node.prev = null;
        }

        @Override
        public String toString() {
            StringBuffer sb = new StringBuffer("[");
            Node<K,V> tempTail = tail;
            while ((tempTail != null)){
                sb.append(" "+tempTail.key);
                tempTail = tempTail.prev;
                sb.append(",");
            }
            sb.append("]");
            return sb.toString();
        }

    }

    private Map<Integer, Node<Integer, Integer>> nodeMap;
    private DoubleLinkList<Integer, Integer> linkList;
    private int capacity;

    public MyLRUCacheDemo(int capacity) {
        this.capacity = capacity;
        nodeMap = new HashMap<>();
        linkList = new DoubleLinkList<>();
    }

    public int get(int key) {
        if (!nodeMap.containsKey(key))
            return -1;

        Node<Integer, Integer> node = nodeMap.get(key);
        linkList.remove(node);
        linkList.addHead(node);
        // 顺序应该要变
        return node.val;
    }

    public void put(int key, int value) {
        Node<Integer, Integer> newNode = new Node<>(key,value);
        if (nodeMap.containsKey(key)){
            // 证明链表中有数据
            Node<Integer, Integer> oldNode = nodeMap.get(key);
            nodeMap.put(key, newNode);
            linkList.remove(oldNode);
            linkList.addHead(newNode);
        }else {
            if (nodeMap.size() >= capacity) {
                Node<Integer, Integer> tail = linkList.tail;
                nodeMap.remove(tail.key);
                linkList.remove(tail);
            }
            nodeMap.put(key, newNode);
            linkList.addHead(newNode);
        }
    }

    public static void main(String[] args){

        MyLRUCacheDemo lruCache = new MyLRUCacheDemo(3);

        lruCache.put(1, 1);
        lruCache.put(2, 2);
        lruCache.put(3, 3);
        lruCache.put(4, 4);

        System.out.println(lruCache.linkList);

        lruCache.put(1, 1);

        System.out.println(lruCache.linkList);

        lruCache.get(3);
        System.out.println(lruCache.linkList);
    }
}
